package 回溯算法;

import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class 复原IP地址 {
      class Solution{
          List<String> result = new ArrayList<>();

          public List<String> restoreIpAddresses(String s){
              if (s.length()>12) return result;
              backTrack(s,0,0);
              return result;
          }

          public void backTrack(String s, int startIndex, int pointnum) {
              if (pointnum == 3){
                  //检索第四段的是否合法
                  if (isValid(s,startIndex,s.length()-1)){
                        result.add(s);
                  }
                  return;
              }
              for (int i = startIndex; i < s.length(); i++) {
                  if (isValid(s,startIndex,i)){
                      //若substring参数只有一个意思就是从当前这个位置加到最后一个
                      s = s.substring(0,i+1) + '.' + s.substring(i+1);
                      pointnum++;
                      //插入逗号后下一个字符串的起始位置为i+2
                      backTrack(s,i+2,pointnum);
                      pointnum--;
                      s = s.substring(0,i+1) + s.substring(i+2);
                  }else {
                      break;
                  }

              }
          }

          private boolean isValid(String s, int start, int end) {
              if (start>end) return false;
              if (s.charAt(start)=='0' && start!=end) return false;
              int num = 0;
              for (int i = start; i <= end; i++) {
                  if (s.charAt(i)>'9'||s.charAt(i)<'0') return false; //遇到非法数据
                  num = num*10 + (s.charAt(i) - '0') ;
                  if (num>255){
                      return false;
                  }
              }
              return true;
          }

      }


}
